package java_class;

/**
 * 辗转相除法
 */
public class demo002 {
    public static void main(String[] arge){
        System.out.println(getGreatestCommonDivisor(100,40));
    }
//    /**
//     * 循环遍历
//     */
//    public static int getGreatestCommonDivisor(int numberA, int numberB){
//        int max = Math.max(numberA,numberB);
//        int min = Math.min(numberA,numberB);
//        // 可以整除时，直接使用
//        if(max%min == 0){return min;}
//        // 循环遍历
//        for (int i = min / 2; i > 0; i--) {
//            if(numberA % i == 0 && numberB % i == 0) return i;
//        }
//        return 1;
//    }

//    /**
//     * 递归遍历
//     * 欧几里何算法
//     * 两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数。
//     */
//    public static int getGreatestCommonDivisor(int numberA, int numberB){
//        return gcd(Math.max(numberA,numberB), Math.min(numberA,numberB));
//    }
//    public static int gcd(int numberA, int numberB){
//        if (numberA % numberB == 0){
//            return numberB;
//        }else{
//            return gcd(numberB, numberA % numberB);
//        }
//    }

    /**
     * 递归遍历
     * 九章算术
     * 两个正整数a和b（a>b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。
     */
    public static int getGreatestCommonDivisor(int numberA, int numberB){
        return gcd(Math.max(numberA,numberB), Math.min(numberA,numberB));
    }
    public static int gcd(int numberA, int numberB){
        if (numberA % numberB == 0){
            return numberB;
        }else{
            return gcd(numberB, Math.abs(numberA - numberB));
        }
    }
}
